package fangpian.leecode

/* 88. 合并两个有序数组 [简单]

知识点：数组、逆向双指针

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。
*/
fun main() {
    // 补充完整
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        if (n == 0) return
        var num1LastIndex = m - 1
        var num2LastIndex = n - 1
        for (i in (m + n - 1) downTo 0) {
            if (num1LastIndex < 0
                || (num2LastIndex >= 0 && nums2[num2LastIndex] > nums1[num1LastIndex])
            ) {
                nums1[i] = nums2[num2LastIndex--]
            } else {
                nums1[i] = nums1[num1LastIndex--]
            }
        }
    }

    // 感觉有点像插入排序
    val a = intArrayOf(1, 2, 3, 0, 0, 0)
    merge(a, 3, intArrayOf(2, 5, 6), 3)
    println(a.contentEquals(intArrayOf(1, 2, 2, 3, 5, 6)))

    val b = intArrayOf(1)
    merge(b, 1, intArrayOf(), 0)
    println(b.contentEquals(intArrayOf(1)))

    val c = intArrayOf(0)
    merge(c, 0, intArrayOf(1), 1)
    println(c.contentEquals(intArrayOf(1)))
}